package LeetCode14;


import java.util.HashMap;
import java.util.Map;

/**
 * @author ：wangchao
 * @version ：V1.0
 * @program ：myLeetCode
 * @date ：Created in 2020/4/3 8:42
 * @description ：LRUCache
 */

/*运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

        获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
        写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

        进阶:

        你是否可以在 O(1) 时间复杂度内完成这两种操作？*/
/*LRUCache cache = new LRUCache( 2 *//* 缓存容量 *//* );

        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回  1
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        cache.get(2);       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        cache.get(1);       // 返回 -1 (未找到)
        cache.get(3);       // 返回  3
        cache.get(4);       // 返回  4*/

public class LRUCache {
    Map<String, LinkNode> map;
    String first;
    String last;
    Integer capacity;
    Integer size;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
        this.size = 0;
    }

    public int get(String key) {
        LinkNode<NodeDate> linkNode = map.get(key);
        int result;
        if (linkNode == null) {
            result = -1;
        } else {
            result = linkNode.getDate().getValue();
            LinkNode<NodeDate> next = linkNode.getNext();
            LinkNode<NodeDate> previous = linkNode.getPrevious();
            if (previous != null) {
                previous.setNext(next);
            }
            if (next != null) {
                next.setPrevious(previous);
            }else{
                NodeDate date = (NodeDate)linkNode.getPrevious().getDate();
                last = date.getKey();
            }

            LinkNode<NodeDate> linkNode1 = map.get(first);
            linkNode.setPrevious(null);
            linkNode.setNext(linkNode1);
            linkNode1.setPrevious(linkNode);
            first = key;
        }
        return result;
    }

    public void put(String key, int value) {
        LinkNode<NodeDate> node = new LinkNode();
        NodeDate nodeDate = new NodeDate();
        nodeDate.setKey(key);
        nodeDate.setValue(value);
        node.setDate(nodeDate);
        if (null == first) {
            node.setPrevious(null);
            node.setNext(null);
            map.put(key, node);
            size++;
            last=key;
        } else {
            if (size < capacity) {
                LinkNode<NodeDate> linkNode = map.get(first);
                node.setNext(linkNode);
                node.setPrevious(null);
                linkNode.setPrevious(node);
                size++;
                map.put(key, node);
            } else {

                LinkNode<NodeDate> lastLinkNode = map.get(last);
                LinkNode<NodeDate> previous = lastLinkNode.getPrevious();
                previous.setNext(null);
                map.remove(last);
                last = previous.getDate().getKey();

                LinkNode<NodeDate> linkNode = map.get(first);
                node.setNext(linkNode);
                node.setPrevious(null);
                map.put(key, node);
            }
        }
        first = key;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put("zhangsan",11);
        lruCache.put("lisi",22);
        lruCache.put("wangwu",33);
        //int zhangsan = lruCache.get("zhangsan");
        lruCache.put("zhaoliu",44);
        int lisi = lruCache.get("lisi");
        int zhangsan = lruCache.get("zhangsan");
        System.out.println("+++++++++++++");
        System.out.println(lisi);
        System.out.println(zhangsan);

    }
}


/**
 * @author ：wangchao
 * @version ：V1.0
 * @program ：myLeetCode
 * @date ：Created in 2020/4/3 17:55
 * @description ：链表节点
 */

 class LinkNode<E> {

    private E date;
    private LinkNode previous;
    private LinkNode next;

    public E getDate() {
        return date;
    }

    public void setDate(E date) {
        this.date = date;
    }

    public LinkNode getPrevious() {
        return previous;
    }

    public void setPrevious(LinkNode previous) {
        this.previous = previous;
    }

    public LinkNode getNext() {
        return next;
    }

    public void setNext(LinkNode next) {
        this.next = next;
    }
}

/**
 * @author ：wangchao
 * @version ：V1.0.1
 * @program ：myLeetCode
 * @date ：Created in 2020/4/3 18:53
 * @description ：节点数据类型
 */
class NodeDate {
    private String key;
    private Integer value;

    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
}